﻿//https://leetcode.cn/problems/maximum-number-of-eaten-apples/

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days)
    {
        // 最小堆，存储 (腐烂时间, 苹果数量)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        int day = 0;
        int n = apples.size();
        int ret = 0;
        while (day < n || !q.empty())
        {
            //当天存在新加入的苹果
            if (day < n && apples[day]>0)
            {
                q.push({ day + days[day],apples[day] });
            }

            //移除已经腐烂的苹果
            while (!q.empty() && q.top().first <= day)
            {
                q.pop();
            }

            //吃掉一个苹果
            if (!q.empty())
            {
                auto top = q.top();
                q.pop();
                ret++;
                if (top.second > 1)
                {
                    q.push({ top.first,top.second - 1 });
                }
            }
            day++;
        }

        // //n天后，苹果不再生产
        // while(!q.empty())
        // {
        //     //移走腐烂的苹果
        //     while(!q.empty()&&q.top().first<=day)
        //     {
        //         q.pop();
        //     }
        //     //没有苹果
        //     if(q.empty())
        //     {
        //         break;
        //     }
        //     //吃掉苹果
        //     auto top=q.top();
        //     q.pop();
        //     ret+=min(top.first-day,top.second);
        //     day+=min(top.first-day,top.second);
        // }
        return ret;
    }
};